P6156 简单题

$\sum_{i=1}^n \sum_{j=1}^n (i+j)^k f(\gcd(i,j)) \gcd(i,j)$

显然 $f(i)=\mu^2(i)$

$\sum_{i=1}^n \sum_{j=1}^n (i+j)^k \mu^2(\gcd(i,j)) \gcd(i,j)$

$\sum_{d=1}^n\sum_{i=1}^n \sum_{j=1}^n [\gcd(i,j)=d](i+j)^k \mu^2(d) d$

$\sum_{d=1}^n d^{k+1}\mu^2(d)\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{n}{d} \rfloor} [\gcd(i,j)=1](i+j)^k$

$\sum_{d=1}^n d^{k+1}\mu^2(d)\sum_{t=1}^{\lfloor \frac{n}{d} \rfloor}\mu(t)t^k\sum_{i=1}^{\lfloor \frac{n}{td} \rfloor} \sum_{j=1}^{\lfloor \frac{n}{td} \rfloor}(i+j)^k$

$\sum_{d=1}^n \sum_{t=1}^{\lfloor \frac{n}{d} \rfloor}(dt)^{k}\mu^2(d)\mu(t)d\sum_{i=1}^{\lfloor \frac{n}{td} \rfloor} \sum_{j=1}^{\lfloor \frac{n}{td} \rfloor}(i+j)^k$

令 $T=td ~,~ S(n)=\sum_{i=1}^n\sum_{j=1}^n(i+j)^k$

$\sum_{T=1}^n S( \lfloor \frac{n}{T} \rfloor) T^k\sum_{d|T} d\mu^2(d)\mu(\frac{T}{d})$

令 $f(n)=\sum_{d|n} d\mu^2(d)\mu(\frac{n}{d})$

$\sum_{T=1}^n S( \lfloor \frac{n}{T} \rfloor) T^kf(T)$

推导的部分就结束了。

将$S(n)$换一种写法：

$S(n)=\sum_{i=1}^{2n} a_ii^k$

其中 $a_i$ 为 $i^k$ 出现的次数。可以发现：

$a_i=\begin{cases} i-1 & i\le n \\ 2n-i+1 & i>n \end{cases}$

再令 $t(n)=\sum_{i=1}^n\sum_{j=1}^i j^k=\sum_{i=1}^n (n-i+1)i^k$

对比系数发现: $S(n)=t(2n)-2t(n)$

另外一个 $f$ 是一个积性函数，可以线筛。

#include <cstdio>
#define Mod 998244353

const int MAXN = 1e7;
int n , k , cnt , prime[ MAXN + 5 ] , f[ MAXN + 5 ] , s[ MAXN + 5 ];
bool vis[ MAXN + 5 ];

int Quick_pow( int x , int po ) {
    int Ans = 1;
    for( ; po ; po >>= 1 , x = 1ll * x * x % Mod )
        if( po & 1 ) Ans = 1ll * Ans * x % Mod;
    return Ans;
}

void sieve( ) {
    f[ 1 ] = s[ 1 ] = 1;
    for( int i = 2 ; i <= MAXN ; i ++ ) {
        if( !vis[ i ] ) {
            prime[ ++ cnt ] = i;
            s[ i ] = Quick_pow( i , k );
            f[ i ] = i - 1;
        }
        for( int j = 1 ; j <= cnt && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
            vis[ i * prime[ j ] ] = 1;
            s[ i * prime[ j ] ] = 1ll * s[ i ] * s[ prime[ j ] ] % Mod;
            if( i % prime[ j ] == 0 ) {
                if( i / prime[ j ] % prime[ j ] != 0 )
                    f[ i * prime[ j ] ] = ( 1ll * -prime[ j ] * f[ i / prime[ j ] ] % Mod + Mod ) % Mod;
                break;
            } 
            f[ i * prime[ j ] ] =  1ll * f[ i ] * f[ prime[ j ] ] % Mod;
        }
    } 
    for( int i = 2 ; i <= MAXN ; i ++ ) {
        f[ i ] = ( 1ll * f[ i ] * s[ i ] % Mod + f[ i - 1 ] ) % Mod;
        s[ i ] = ( s[ i ] + s[ i - 1 ] ) % Mod;
    }
    for( int i = 2 ; i <= MAXN ; i ++ )
        s[ i ] = ( s[ i ] + s[ i - 1 ] ) % Mod;
}

int Sum( int n ) {
    return ( ( s[ 2 * n ] - 2ll * s[ n ] ) % Mod + Mod ) % Mod;
}

int Solve( int n ) {
    int Ans = 0;
    for( int l = 1 , r ; l <= n ; l = r + 1 ) {
        r = n / ( n / l );
        Ans = ( Ans + 1ll * ( f[ r ] - f[ l - 1 ] + Mod ) % Mod * Sum( n / l ) % Mod ) % Mod;
    }
    return Ans;
}

int main( ) {
    long long t;
    scanf("%d %lld",&n,&t); k = t % ( Mod - 1 );
    sieve( );
    printf("%d\n", Solve( n ) );
    return 0;
}